import com.sun.source.tree.Tree;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 张宇田
 * Date: 2025-04-08
 * Time: 10:34
 */
public class BinarySearchTree {
    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        public TreeNode(int val){
            this.val = val;
        }
    }

    private TreeNode root = null;
    //找到返回val的节点
    public TreeNode search(int key) {
        if(root == null){
            return null;
        }
        TreeNode cur = root;
        while(cur != null){
            if (key > cur.val){
                cur = cur.right;
            }else if(key < cur.val){
                cur = cur.left;
            }else{
                return cur;
            }
        }
        //走完循环没找到就说明没有
        return null;
    }


    /*插入
    *数字的插入顺序不同，
    *最终生成的二 叉搜索树（BST）的结构可能会不同，
    * 但它们的中序遍历结果一定相同
    */
    public boolean insert(int key){
        TreeNode node = new TreeNode(key);
        if(root == null){
            root = node;
            return true;
        }
        TreeNode cur = root;
        TreeNode curParent = null;
        while (cur != null){
            if(key > cur.val){
                curParent = cur;
                cur = cur.right;
            }else if(key < cur.val){
                curParent = cur;
                cur = cur.left;
            }else{
                return false;
            }

        }
        //走到这里cur已经是空了
        if(key > curParent.val){
             curParent.right = node ;
        }else {
             curParent.left = node;
        }
        return true;
    }
}
